/********************************************************************************
 * @Author: Zhenzhou Liu
 * @Date: 2024-12-29
 * @Description: Cg图论练习之判断无向图的连通性
 *******************************************************************************/
#include <iostream>
#include <vector>

using namespace std;

void dfs(const vector<vector<int>> & adj, vector<bool> & visited, int u) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(adj, visited, v);
        }
    }
}

bool judgeConnectivity(const vector<vector<int>> & adj, int n) {
    vector<bool> visited(n + 1, false);

    int start = 1;
    for (int i = 1; i <= n; i++) {
        if (!adj[i].empty()) {
            start = i;
            break;
        }
    }
    dfs(adj, visited, start);
    for (int i = 1; i <= n; i++) {
        if (!visited[i])
            return false;
    }
    return true;
}

int main(int argc, char *argv[]) {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    int u, v;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    cout << (judgeConnectivity(adj, n) ? 1 : 0);
    return 0;
}

/*Test Case1
3 3
1 2
2 3
3 1
*/




